package com.java.comprehensive.arithmetic.leecode.easy;

import util.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: comprehensive-service
 * @description: 将有序数组转换为二叉搜索树
 * @author: 窦绍飞
 * @create: 2021-12-01 14:15
 **/
public class LeetCode_108 {
	//数组时有序的话 那么 前面时最小的
	//最小的树 是二叉树距离根节点最近的地方

	public static TreeNode sortedArrayToBST(int[] nums) {

		return helper(nums, 0, nums.length - 1);
	}

	public static TreeNode helper(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}

		// 总是选择中间位置左边的数字作为根节点
		int mid = (left + right) / 2;

		TreeNode root = new TreeNode(nums[mid]);
		root.left = helper(nums, left, mid - 1);
		root.right = helper(nums, mid + 1, right);
		return root;
	}


	public TreeNode sortedArrayToBST_(int[] nums) {
		return is(nums, 0, nums.length - 1);
	}

	public TreeNode is(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}
		int mid = (left+right)/ 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = is(nums, left, mid - 1);
		root.right = is(nums, mid + 1, right);
		return root;
	}
	public static void main(String[] args) {
		int[] nums = {-10, -3, 0, 5, 9};
		System.out.println(sortedArrayToBST(nums));
	}
}
